import java.util.ArrayList;
import java.util.List;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/21
 * \* Time: 22:03
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 二叉树展开为链表 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 时间O(N),空间O(N)
     * @param root
     */
    public void flatten(TreeNode root) {
        List<TreeNode> list=new ArrayList<>();
        preOrder(root,list);
        int size=list.size();
        for(int i=1;i<size;i++){
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preOrder(TreeNode root, List<TreeNode> list){
        if(root!=null){
            list.add(root);
            preOrder(root.left,list);
            preOrder(root.right,list);
        }
    }

    /**
     * 对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，
     * 将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，
     * 并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。
     *时间O(n),空间O(1)
     * @param root
     */
    public void flatten1(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }
    }

    /**
     * 做法2：递归
     * @param root
     */
    public void flatten2(TreeNode root) {
        if(root==null){
            return ;
        }
        flatten(root.left);
        flatten(root.right);

        TreeNode left=root.left;
        TreeNode right=root.right;
        root.left=null;
        root.right=left;
        TreeNode p=root;
        while(p.right!=null){
            p=p.right;
        }
        p.right=left;
    }


}